// https://leetcode.cn/problems/longest-palindromic-substring/description/

// 算法思路总结：
// 1. 中心扩展法寻找最长回文子串
// 2. 遍历每个字符，考虑奇数和偶数长度两种情况
// 3. 奇数：以单个字符为中心向两边扩展
// 4. 偶数：以两个相同字符为中心向两边扩展
// 5. 记录扩展过程中的最大长度和对应子串
// 6. 时间复杂度：O(n²)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <string>
#include <vector>

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        int m = s.size();
        if (m == 1) return s;
        int len = 0;
        string res;

        for (int i = 0 ; i < m ; i++)
        {
            int l = i, r = i;
            while (l - 1 >= 0 && r + 1 < m && s[l - 1] == s[r + 1])
                l--, r++;
            if (r - l + 1 > len)
            {
                len = max(len, r - l + 1);
                res = s.substr(l, len);
            }

            l = i, r = i + 1;
            while (l > -1 && r < m && s[l] == s[r])
                l--, r++;
            if (r - l - 1 > len)
            {
                len = max(len, r - l - 1);
                res = s.substr(l + 1, r - l - 1);
            }
        }
        
        return res;
    }
};

int main()
{
    string s1 = "babad", s2 = "cbbd";
    Solution sol;

    cout << sol.longestPalindrome(s1) << endl;
    cout << sol.longestPalindrome(s2) << endl;

    return 0;
}